// 动态规划版
// 2742 给墙壁刷油漆
// https://leetcode.cn/problems/painting-the-walls/description/?envType=daily-question&envId=2024-06-28

/**
 * 给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
请你返回刷完 n 堵墙最少开销为多少。

示例 1：

输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。
示例 2：

输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。
 */

/**
 * @param {number[]} cost
 * @param {number[]} time
 * @return {number}
 */
var paintWalls = function (cost, time) {
    let info = [];
    cost.forEach((val, i) => {
        info.push({
            cost: val,
            time: time[i],
        });
    });

    info.sort((a, b) => {
        if (a.cost != b.cost) {
            return a.cost - b.cost;
        }

        return b.time - a.time;
    });

    console.log(`${'-'.repeat(30)}`);
    // console.log(`sorted: ${JSON.stringify(info)}`);

    let remainInfo = info;
    let currentCost = 0;
    let currentTime = 0;
    let level = 0;
    let count = 0;

    totalCost = dfs(
        remainInfo,
        currentCost,
        currentTime,
        level,
        count,
        Number.MAX_SAFE_INTEGER
    );

    console.log(`totalCost: ${totalCost}`);
    return totalCost;
};

function dfs(remainArr, curCost, curTime, dfsIndex, count, bestCost) {
    if (curCost >= bestCost) {
        return bestCost;
    }

    if (remainArr.length - count <= curTime) {
        if (curCost < bestCost) {
            bestCost = curCost;
        }

        return bestCost;
    }

    for (let i = dfsIndex; i < remainArr.length / 2; i++) {
        let thisCost = curCost + remainArr[i].cost;
        let thisTime = curTime + remainArr[i].time;

        let newCost = dfs(
            remainArr,
            thisCost,
            thisTime,
            i + 1,
            count + 1,
            bestCost
        );

        if (newCost < bestCost) {
            bestCost = newCost;
        }
    }

    return bestCost;
}

paintWalls([1, 2, 3, 2], [1, 2, 3, 2]); // 3
paintWalls([2, 3, 4, 2], [1, 1, 1, 1]); // 4
paintWalls([49, 35, 32, 20, 30, 12, 42], [1, 1, 2, 2, 1, 1, 2]); // 62
paintWalls([8, 7, 5, 15], [1, 1, 2, 1]); // 12
paintWalls([26, 53, 10, 24, 25, 20, 63, 51], [1, 1, 1, 1, 2, 2, 2, 1]); // 55
paintWalls(
    [7, 15, 38, 35, 61, 90, 34, 29, 68, 35],
    [1, 1, 3, 3, 2, 1, 3, 1, 2, 3]
); // 76
paintWalls(
    [
        996, 1453, 1153, 1277, 92, 2107, 10, 2442, 1773, 1266, 927, 1166, 983,
        2339, 2382, 443, 928, 1674, 1704, 633, 20, 649, 914, 147, 2379, 385,
        2330, 969, 1659, 1018, 2262, 1563, 1583, 1191, 1524, 1677, 2288, 1951,
        1420, 2125, 1861, 1316, 2149, 1306, 145, 492, 837, 2019, 1578, 784,
    ],
    [
        6, 6, 1, 6, 2, 4, 3, 6, 6, 5, 4, 7, 3, 5, 4, 2, 4, 7, 2, 7, 5, 2, 4, 5,
        7, 2, 5, 2, 1, 7, 5, 5, 2, 7, 2, 5, 5, 6, 7, 3, 2, 6, 4, 4, 4, 2, 1, 6,
        7, 3,
    ]
); // 3446
paintWalls(
    [
        1782, 7431, 1625, 7072, 3109, 6514, 6297, 24, 3929, 8900, 5120, 7935,
        3700, 1690, 8295, 822, 1051, 5606, 5607, 2990, 4824, 2743, 7300, 8236,
        6037, 6649, 1586, 6716, 5245, 7513, 1935, 6953, 6139, 4625, 3518, 8565,
        5169, 1372, 1110, 3203, 7317, 8577, 3212, 4391, 1451, 1783, 3003, 4794,
        7001, 6734, 7778, 2497, 6825, 2885, 6009, 399, 5409, 5396, 6689, 4699,
        7737, 8474, 8159, 6676, 7812, 1968, 3187, 4534, 7028, 6484, 8642, 8674,
        7837, 4925, 23, 3816, 1062, 5682, 7455, 6237, 8735, 3755, 5918, 6712,
        1724, 3266, 6846, 1507, 1772, 1221, 7051, 1908, 4812, 3031, 2187,
    ],
    [
        6, 8, 5, 8, 2, 6, 3, 1, 4, 9, 6, 1, 7, 4, 2, 2, 5, 6, 6, 5, 7, 6, 4, 4,
        2, 6, 7, 8, 3, 2, 2, 3, 2, 7, 2, 7, 7, 5, 7, 3, 6, 9, 1, 1, 6, 7, 3, 7,
        3, 3, 2, 9, 9, 1, 2, 7, 7, 1, 1, 7, 3, 4, 6, 4, 2, 2, 8, 1, 1, 9, 3, 8,
        4, 6, 2, 8, 4, 2, 1, 3, 7, 3, 7, 5, 9, 1, 7, 4, 8, 3, 2, 4, 5, 6, 4,
    ]
);
// 17361
